package chapter05_string;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 描述：
 *      公式字符串求值
 *      给定一个字符串str,str表示一个公式，公式里可能有整数、加减乘除符号和左右括号,返回公式的计算结果。
 *
 *      说明：
 *          1）可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。
 *          2）如果是负数，就需要用括号括起来，比如"4*(-3)"。 但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如"-3*4"和"(-3*4)" 都是合法的。
 *          3)不用考虑计算过程中会发生溢出的情况。
 * @author hl
 * @date 2021/9/11 11:29
 */
public class GetValueOfFormula {
    public static void main(String[] args) {
        String expression = "48*((70-65)-43)+8*1";
        GetValueOfFormula main = new GetValueOfFormula();
        int res = main.getValue(expression);
        System.out.println(res);
    }
    /**
     * 重点在于如果没有括号的时候求值的流程应该是怎么样的，有括号无非就是加一层递归而已
     * 无括号的处理需要注意
     * 如何处理负数？  不特别去处理负数，而是将负数看作运算符-
     * 如何处理优先级？ 用栈，遇到乘除直接计算，遇到+-压入栈，也就是栈中只存放+-运算的式子，遍历完成后统一计算
     * @return
     */
    public int getValue(String str){
        return getValueNoBracket(str, 0)[0];
    }

    /**
     * 遇到括号进行递归，在处理过程中可以按照没有括号的式子来进行处理
     * @param str
     * @return
     */
    public int[] getValueNoBracket(String str, int i){
        //转存转换后的+-式子
        Deque<String> deque = new LinkedList<>();
        int pre = 0, res = 0;
        while (i < str.length() && str.charAt(i) != ')') {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                pre = pre * 10 + (str.charAt(i++) - '0');
            }else if (str.charAt(i) != '(') {
                addNum(deque, pre);
                deque.addLast(String.valueOf(str.charAt(i++)));
                pre = 0;
            }else{
                int[] arr = getValueNoBracket(str, i + 1);
                pre = arr[0];
                i = arr[1] + 1;
            }
        }
        addNum(deque, pre);
        return new int[] {getSum(deque), i};
    }

    private int getSum(Deque<String> deque) {
        int res = 0;
        String cur = null;
        boolean add = true;
        while(!deque.isEmpty()){
            cur = deque.pollFirst();
            if (cur.equals("+")) {
                add = true;
            }else if (cur.equals("-")) {
                add = false;
            }else{
                res = add ? res + Integer.parseInt(cur) : res - Integer.parseInt(cur);
            }
        }
        return res;
    }

    public void addNum(Deque<String> deque, Integer num){
        int tmp = 0;
        if (!deque.isEmpty()) {
            String symbol = deque.pollLast();
            if (symbol.equals("+") || symbol.equals("-")) {
                deque.addLast(symbol);
                deque.addLast(String.valueOf(num));
            }else{
                tmp = Integer.parseInt(deque.pollLast());
                if (symbol.equals("*")) {
                    deque.addLast(String.valueOf(num * tmp));
                }else{
                    deque.addLast(String.valueOf(num / tmp));
                }
            }
            return;
        }
        deque.addLast(String.valueOf(num));
    }

    public int calculate(String str1, String str2, char symbol){
        Integer n1 = Integer.valueOf(str1);
        Integer n2 = Integer.valueOf(str1);
        if(symbol == '+'){
            return n1 + n2;
        }else if (symbol == '-') {
            return n1 - n2;
        }else if(symbol == '*'){
            return n1 * n2;
        }else if (symbol == '/') {
            return n1 / n2;
        }
        throw new RuntimeException("no support symbol: " + symbol);
    }

}
